#include <stdio.h>
#include <stdlib.h>

struct tree
{
  char data;
  struct tree * lchild;
  struct tree * rchild;
};

struct tree * creat()
{
  struct tree * btree[100];
  struct tree * node;
  struct tree * root;
  int front, rear;
  char ch;

  front = 1;
  rear = 0;
  root = NULL;

  scanf("%c", &ch);
  while (ch != '#') {
    node = NULL;
    if (ch != ',') {
      node = (struct tree *) malloc (sizeof(struct tree));
      node->data = ch;
      node->lchild = NULL;
      node->rchild = NULL;
    }
    rear++;
    btree[rear] = node;

    if (rear == 1)
      root = node;
    else {
      if ((node != NULL) && (btree[front] != NULL)) {
	if (rear % 2 == 0) 
	  btree[front]->lchild = node;
 	else 
	  btree[front]->rchild = node;
      }

      if (rear % 2 == 1) 
	front++;
    }

    scanf("%c", &ch);
  }

  return root;
}

// 前根遍历
void preorder_r(struct tree * root)
{
  struct tree * src;

  src = root;
  if (src != NULL) {
    printf(" %c ", src->data);
    preorder_r(src->lchild);
    preorder_r(src->rchild);
  }
}

void preorder(struct tree * root) 
{
  struct tree * src, * stack[100];
  int top = 0;

  src = root;
  while ((src != NULL) || (top > 0)) {
    while (src != NULL) {
      printf(" %c ", src->data);
      stack[++top] = src;
      src = src->lchild;
    }
    src = stack[top--];
    src = src->rchild;
  }
}

// 中根遍历
void inorder_r(struct tree * root)
{
  struct tree * src;

  src = root;
  if (src != NULL) {
    inorder_r(src->lchild);
    printf(" %c ", src->data);
    inorder_r(src->rchild);
  }
}

void inorder(struct tree * root)
{
  struct tree * src, * stack[100];
  int top = 0;

  src = root;
  while ((src != NULL) || (top > 0)) {
    while (src != NULL) {
      stack[++top] = src;
      src = src->lchild;
    }
    src = stack[top--];
    printf(" %c ", src->data);
    src = src->rchild;
  }
}

// 后根遍历
void postorder_r(struct tree * root)
{
  struct tree * src;

  src = root;
  if (src != NULL) {
    postorder_r(src->lchild);
    postorder_r(src->rchild);
    printf(" %c ", src->data);
  }
}

void postorder(struct tree * root)
{
  struct tree * src, * stack[100];
  int top = 0;
  int stack2[100], b;

  src = root;
  do {
    while (src != NULL) {
      stack[top] = src;
      stack2[top++] = 0;
      src = src->lchild;
    }
    if (top > 0) {
      b = stack2[--top];
      src = stack[top];
      if (b == 0) {
	stack[top] = src;
	stack2[top++] = 1;
	src = src->rchild;
      }
      else {
	printf(" %c ", src->data);
	src = NULL;
      }
    }
  } while (top > 0);
}

// 二叉树高度
int treehigh(struct tree * root)
{
  int h, lh, rh;

  if (root == NULL)
    h = 0;
  else {
    lh = treehigh(root->lchild);
    rh = treehigh(root->rchild);
    if (lh >= rh)
      h = lh + 1;
    else
      h = rh + 1;
  }

  return h;
}

// 以先序遍历来实现查找
struct tree * traverse(struct tree * root, char x)
{
  struct tree * src;

  src = NULL;
  if ((root != NULL))
    if (root->data == x) {
      src = root;
      return src;
    }
    else {
      traverse(root->lchild, x);
      traverse(root->rchild, x);
    }
}

struct tree * find(struct tree * root, char x)
{
  struct tree * ptr;

  ptr = traverse(root, x);

  return ptr;
}

/* 叶子数目 */
int leaf(struct tree * root, int n)
{
  if (root != NULL) {
    if ((root->lchild == NULL) && (root->rchild == NULL))
      n++;
    n = leaf(root->lchild, n);
    n = leaf(root->rchild, n);
  }
}

void lorder(struct tree * root)
{
  struct tree * src[100], * p;
  int front, rear;

  src[1] = root;
  front = 1;
  rear = 1;

  while (front <= rear) {
    p = src[front];
    front++;

    printf(" %d ", p->data);
    
    if (p->lchild != NULL) {
      rear++;
      src[rear] = p->lchild;
    }

    if (p->rchild != NULL) {
      rear++;
      src[rear] = p->rchild;
    }
  }
}

int main()
{
  struct tree * root;
  struct tree * des;

  root = creat();

  preorder(root);  printf("\n");
  inorder_r(root);   printf("\n");
  postorder_r(root); printf("\n");

  //des = find(root , 'D');
  //printf("%c", des->data);
  
}
